package com.leetcode.tree.recursion;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/6/15 17:03
 */
public class HasPathSum_112 {

    private boolean result = false;

    public boolean hasPathSum1(TreeNode root, int sum) {
        search(root, sum);
        return result;
    }

    // 常规方法，构建一个额外的递归
    public void search(TreeNode root, int sum) {
        if (root == null) return;
        sum -= root.val;
        if (sum == 0 && root.left == null && root.right == null)
            result = true;
        search(root.left, sum);
        search(root.right, sum);
    }

    // 简化版。通过离散数学关系分析，这是一个析取关系，只要有一个为true，则结果为true
    public boolean hasPathSum2(TreeNode root, int sum) {
        // 通过false终止递归
        if (root == null)
            return false;
        // 这里是与root val相等，而不是0，注意
        if (sum == root.val && root.left == null && root.right == null)
            return true;
        // 结果为析取形式，只有一条路径满足长度需求，那么可以得到结果是正确的
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.right == null && root.left == null && root.val == sum) return true;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.left, sum - root.val);
    }


}
